package com.datastructures2.search;

import com.datastructures2.背包队列栈.Queue;

/**
 * N个键的有序数组最多需要lgN+1次比较
 * @author MaoLin Wang
 * @date 2020/3/118:43
 */
public class BinarySearchST<Key extends Comparable<Key>,Value> {
    private Key[] keys;
    private Value[] values;
    private int size;

    public BinarySearchST(int size) {
        keys= (Key[]) new Comparable[size];
        values= (Value[]) new Comparable[size];
    }
    public int Size(){
        return size;
    }

    public Value get(Key key){
        if (isEmpty()){
            return null;
        }
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            return values[i];
        }else {
            return null;
        }
    }

    public void put(Key key,Value value){
        if (key==null){
            return;
        }
        if (value==null){
            delete(key);
            return;
        }
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            //存在key，则更新值
            values[i]=value;
        }else {
            if (size == keys.length) resize(2*keys.length);

            //不存在，则将从i到size的所有元素向后移动一个位置，再将新的值加入到位置i
            for (int j = size; j > i; j--) {
                keys[j]=keys[j-1];
                values[j]=values[j-1];
            }
            keys[i]=key;
            values[i]=value;
            size++;
        }
    }

    /**
     * 返回小于给定键key的key的数量
     * @param key
     * @return
     */
    public int rank(Key key){
        int left=0,right=size-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            int result=keys[mid].compareTo(key);
            if (result<0){
                left=mid+1;
            }else if (result > 0){
                right=mid-1;
            }else {
                return mid;
            }
        }
        return left;
    }
    public boolean isEmpty(){
        return size==0;
    }

    public  Key minKey(){
        return keys[0];
    }
    public Key maxKey(){
        return keys[size-1];
    }
    public Key selectKey(int k){
        return keys[k];
    }

    /**
     * 向上取整  找出大于等于该键的最小键
     * @param key
     * @return
     */
    public Key ceiling(Key key){
        int i=rank(key);
        return keys[i];
    }

    /**
     * 向下取整 找出小于等于该键的最小键
     * @param key
     * @return
     */
    public Key floor(Key key){
        if (key==null)throw new IllegalArgumentException("key为空");
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            return keys[i];
        }else if (i==0){
            return null;
        }else {
            return keys[i-1];
        }
    }

    public void delete(Key key){
        if (key==null)throw new IllegalArgumentException("key为空");
        if (isEmpty()) return;

        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            for (int j = i; j < size-1 ; j++) {
                keys[j]=keys[j+1];
                values[j]=values[j+1];
            }
            size--;
            keys[size]=null;
            values[size]=null;

            return ;
        }
    }

    private void resize(int capacity) {
        Key[]   tempKey = (Key[])   new Comparable[capacity];
        Value[] tempValue = (Value[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            tempKey[i] = keys[i];
            tempValue[i] = values[i];
        }
        values = tempValue;
        keys = tempKey;
    }

    public void delMin(){
        delete(minKey());
    }
    public void delMax(){
        delete(maxKey());
    }
    public Iterable<Key> keys(Key lo,Key hi){
        Queue<Key>queue=new Queue<>();
        int right = rank(hi);
        for (int i = rank(lo); i < right; i++) {
            queue.enqueue(keys[i]);
        }
        if (contains(hi)){
            queue.enqueue(keys[right]);
        }
        return queue;
    }
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }

    public static void main(String[] args) {
        BinarySearchST<String,Integer> binarySearchST=new BinarySearchST<>(5);

        binarySearchST.put("a",3);
        binarySearchST.put("d",2);
        binarySearchST.put("c",1);
        binarySearchST.put("b",0);
        binarySearchST.put("e",4);
        System.out.println(binarySearchST.size);
        binarySearchST.delete("b");
        String s = binarySearchST.selectKey(3);
        System.out.println(s);


    }


}
